History monoid

 ( Concurrency ) 

In mathematics and computer science, a history monoid is a way of representing the histories of concurrently running computer processes as a collection of strings, each string representing the individual history of a process. The history monoid provides a set of synchronization primitives (such as locks, or ) for providing rendezvous points between a set of independently executing processes or threads.

History monoids occur in the theory of concurrent computation, and provide a low-level mathematical foundation for process calculi, such as CSP the language of communicating sequential processes, or CCS, the calculus of communicating systems. History monoids were first presented by M.W. Shields.M.W. Shields "Concurrent Machines", Computer Journal, (1985) 28 pp. 449–465.

History monoids are isomorphism to (free partially commutative monoids) and to the monoid of . As such, they are and are universal. The history monoid is a type of semi-abelian categorical product in the category of monoids.

---

Product monoids and projection Let

$A=(\backslash Sigma\_1,\backslash Sigma\_2,\backslash ldots,\backslash Sigma\_n)$

denote an n-tuple of (not necessarily pairwise disjoint) alphabets $\backslash Sigma\_k$. Let $P(A)$ denote all possible combinations of one finite-length string from each alphabet:

$P(A)=\backslash Sigma\_1^*\; \backslash times\; \backslash Sigma\_2^*\; \backslash times\; \backslash cdots\; \backslash times\; \backslash Sigma\_n^*$

(In more formal language, $P(A)$ is the Cartesian product of the of the $\backslash Sigma\_k$. The superscript star is the Kleene star.) Composition in the product monoid is component-wise, so that, for

$\backslash mathbf\{u\}=(u\_1,u\_2,\backslash ldots,u\_n)\; \backslash ,$

and

$\backslash mathbf\{v\}=(v\_1,v\_2,\backslash ldots,v\_n)\; \backslash ,$

then

$\backslash mathbf\{uv\}=(u\_1v\_1,u\_2v\_2,\backslash ldots,u\_nv\_n)\; \backslash ,$

for all $\backslash mathbf\{u\},\; \backslash mathbf\{v\}$ in $P(A)$. Define the union alphabet to be

$\backslash Sigma=\backslash Sigma\_1\; \backslash cup\; \backslash Sigma\_2\; \backslash cup\; \backslash cdots\; \backslash cup\; \backslash Sigma\_n.\; \backslash ,$

(The union here is the set union, not the disjoint union.) Given any string $w\backslash in\; \backslash Sigma^*$, we can pick out just the letters in some $\backslash Sigma\_k^*$ using the corresponding string projection $\backslash pi\_k:\backslash Sigma^*\backslash to\backslash Sigma\_k^*$. A distribution $\backslash pi:\backslash Sigma^*\backslash to\; P(A)$ is the mapping that operates on $w\backslash in\; \backslash Sigma^*$ with all of the $\backslash pi\_k$, separating it into components in each free monoid:

$\backslash pi(w)\backslash mapsto\; (\backslash pi\_1(w),\; \backslash pi\_2(w),\; \backslash ldots\; ,\; \backslash pi\_n(w)).\; \backslash ,$

---

Histories For every $a\backslash in\backslash Sigma$, the tuple $\backslash pi(a)$ is called the elementary history of a. It serves as an indicator function for the inclusion of a letter a in an alphabet $\backslash Sigma\_k$. That is,

$\backslash pi(a)=(a\_1,a\_2,\backslash ldots,a\_n)$

where

$a\_k=\backslash begin\{cases\}$

a \mbox{ if } a\in \Sigma_k \\ \varepsilon \mbox { otherwise }. \end{cases}

Here, $\backslash varepsilon$ denotes the empty string. The history monoid $H(A)$ is the submonoid of the product monoid $P(A)$ generated by the elementary histories: $H(A)\; =\; \backslash \{\; \backslash pi(a)\; |\; a\backslash in\backslash Sigma\; \backslash \}^*$ (where the superscript star is the Kleene star applied with a component-wise definition of composition as given above). The elements of $H(A)$ are called global histories, and the projections of a global history are called individual histories.

---

Connection to computer science The use of the word history in this context, and the connection to concurrent computing, can be understood as follows. An individual history is a record of the sequence of states of a process (or thread or Turing machine); the alphabet $\backslash Sigma\_k$ is the set of states of the process.

A letter that occurs in two or more alphabets serves as a synchronization primitive between the various individual histories. That is, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendezvous" them together.

Consider, for example, $\backslash Sigma\_1=\backslash \{a,b,c\backslash \}$ and $\backslash Sigma\_2=\backslash \{a,d,e\backslash \}$. The union alphabet is of course $\backslash Sigma=\backslash \{a,b,c,d,e\backslash \}$. The elementary histories are $(a,a)$, $(b,\backslash varepsilon)$, $(c,\backslash varepsilon)$, $(\backslash varepsilon,d)$ and $(\backslash varepsilon,e)$. In this example, an individual history of the first process might be $bcbcc$ while the individual history of the second machine might be $ddded$. Both of these individual histories are represented by the global history $bcbdddcced$, since the projection of this string onto the individual alphabets yields the individual histories. In the global history, the letters $b$ and $c$ can be considered to commute with the letters $d$ and $e$, in that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently, and are unordered with respect to each other; they have not (yet) exchanged any messages or performed any synchronization.

The letter $a$ serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters $b$ and $c$ can be re-ordered past $d$ and $e$, they cannot be reordered past $a$. Thus, the global history $bcdabe$ and the global history $bdcaeb$ both have as individual histories $bcab$ and $dae$, indicating that the execution of $d$ may happen before or after $c$. However, the letter $a$ is synchronizing, so that $e$ is guaranteed to happen after $c$, even though $e$ is in a different process than $c$.

---

Properties A history monoid is isomorphic to a trace monoid, and as such, is a type of semi-abelian categorical product in the category of monoids. In particular, the history monoid $H(\backslash Sigma\_1,\backslash Sigma\_2,\backslash ldots,\backslash Sigma\_n)$ is isomorphic to the trace monoid $\backslash mathbb\{M\}(D)$ with the dependency relation given by

$D=\backslash left(\backslash Sigma\_1\backslash times\backslash Sigma\_1\backslash right)\backslash cup$

\left(\Sigma_2\times\Sigma_2\right)\cup \cdots \cup \left(\Sigma_n\times\Sigma_n\right).

In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet $\backslash Sigma\_k$ can be commutatively re-ordered past the letters in an alphabet $\backslash Sigma\_j$, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice versa.

Conversely, given any trace monoid $\backslash mathbb\{M\}(D)$, one can construct an isomorphic history monoid by taking a sequence of alphabets $\backslash Sigma\_\{a,\; b\}\; =\; \backslash \{a,\; b\backslash \}$ where $(a,\; b)$ ranges over all pairs in $D$.

---

Notes

• Antoni Mazurkiewicz, "Introduction to Trace Theory", pp. 3–41, in The Book of Traces, V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore
• Volker Diekert, Yves Métivier, " Partial Commutation and Traces", In G. Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, Vol. 3, Beyond Words, pages 457–534. Springer-Verlag, Berlin, 1997.

Categories: Concurrency, Semigroup Theory, Formal Languages, Free Algebraic Structures

Post Comment